package jun;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-10 14:12
 * @description：
 * @modified By：
 * @version:
 */
public class Jun10 {
    public boolean isMatch(String s, String p) {
        /**
         * create by: 冯涛滔
         * description: https://leetcode-cn.com/problems/wildcard-matching/
         * create time: 2020-6-10 15:05
         * @params [s, p]
         * @return boolean
         */
        char[] list1 = s.toCharArray();
        char[] list2 = p.toCharArray();
        boolean[][] dp = new boolean[list1.length+1][list2.length+1];
        dp[0][0] = true;//初始化
        for (int i = 1; i < dp[0].length; i++) {
            dp[0][i] = list2[i-1]=='*'&&dp[0][i-1]; //初始化第一排 极限情况 list2 = ***** 虽然不知道有什么用
        }
        for (int i = 1; i <= dp.length; i++) {
            for (int j = 1; j <= dp[i].length; j++) {
                //考虑*空串 岁造成 4,3 甚至4,1 为true
                if (list2[j-1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    // 当前位置是 ？,可以匹配任意单个字符，所以和前一个位置结果一样
                    // p当前位置字符和s当前字符一样，所以跟前一个位置匹配结果一样
                } else if (list2[j-1] == '?' || list1[i-1] == list2[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[list1.length][list2.length];
    }
    public boolean isMatch2(String s, String p) {
        // dp[i][j]表示s截止到第i个位置(s[i-1])的子串与p截止到第j个位置(p[j-1])的子串是否匹配
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        // dp[0][0]表示 空s 和 空p 匹配
        dp[0][0] = true;
        // for循环的开始条件是i=1,也就是没考虑 空s 的匹配情况，dp[0][0]只考虑了 空s匹配空p
        // 但 空s 也可以匹配 *,**,而且对于 *abc*, 空s的匹配情况可以简化
        // 这里对空s的匹配情况进行初始化
        for (int j = 1; j <= p.length(); j++) {
            // s匹配*,相当于s匹配空；s匹配**相当于s匹配*；s匹配*cb*相当于s匹配*cb
            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j-1];
        }
        // 注意 i,j表示的是s和p中第几个字符，对应的索引索引是i-1,j-1
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                // 根据模式串的当前位置的字符来分类讨论
                // 当前位置是 *
                // * 可以匹配任意字符包括空字符，所以考虑 dp[i-1][j-1],dp[i-1][j],dp[i][j-1]这前面已处理过的三个结果
                // 但其实 dp[i-1][j-1]不用考虑，因为考虑dp[i-1][j]时也会执行这个if，还是会考虑到dp[i-1][j-1]
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    // 当前位置是 ？,可以匹配任意单个字符，所以和前一个位置结果一样
                    // p当前位置字符和s当前字符一样，所以跟前一个位置匹配结果一样
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        // 返回
        return dp[s.length()][p.length()];
    }
}
